ACL Beginner Contest

https://gyazo.com/cf293b51cdb0f3e61921e381956d2872

うわ、あと9ポイントで水色！惜しい！

https://gyazo.com/9dabf4b98969d40e2b5509564cfe5ff0

https://gyazo.com/f4f4a47bc47a888934ec7935d5699512

ケアレスミスした

大急ぎで直したので不格好な条件式

code:python

A, B, C, D = map(int, input().split())

# if A <= D <= B or A <= C <= B: # NG

if A <= D <= B or A <= C <= B or C <= A <= D:

print("Yes")

else:

print("No")

落ち着いて考えるとこう

code:python

A, B, C, D = map(int, input().split())

if D < A or B < C:

print("No")

else:

print("Yes")

https://gyazo.com/d392de5b2ccc1dc816648fb819b6adbf

繋がってる都市の塊がいくつあるか数えて(Xとする)、その一つから残りX-1個に道を引けば良い

code:python

def solve(N, M, edges):

init_unionfind(N)

for e in edges:

s = set(find_root(x) for x in range(N))

return len(s) - 1

https://gyazo.com/13fcd06d7d09419948c239f846aedff7

どうACLに帰着するのかわからないのでまずは素朴に書く

提出したが WA/TLE混じり

WAが取れてもTLEだろうし、どう解決するか目処が付いてないので一旦保留してEをやった

末尾の値を定義域、最長の長さを値域とする動的計画法

i番目の値がAの時、Aの前後K個の値のmaxが「i番目の値をつなげることのできる最も長い列」なので、それに1足したもので更新

下記でサンプルは通る

code:python

def solve(N, K, AS):

for i in range(1, N):

start = max(0, A - K)

return max(count)

点更新範囲maxなのでセグメント木が使える

セグメント木バージョン AC

code:python

def solve(N, K, AS):

MAX_CAPACITY = 300_000

set_width(MAX_CAPACITY + 10)

for i in range(1, N):

start = max(0, A - K)

end = min(A + K + 1, MAX_CAPACITY + 1)

best = range_reduce(count, start, end, max, -INF)

point_set(count, A, best + 1, max)

return range_reduce(count, 0, MAX_CAPACITY + 1, max, -INF)

ハマりポイント

https://gyazo.com/2bd499438884da4227a67110c503b545

範囲更新するので双対セグメント木かなと思った

二項演算がsizeを引数に取らないので大急ぎで自作ライブラリを手直しした

別解

E は、(長さ、sum）を持ちました。 (10^n, sum) を持った方が mod pow を使わずに済んで計算量が良いと思います。

code:python

def main():

# parse input

N, Q = map(int, input().split())

set_width(N + 1)

value_unity = 0

action_unity = None

cache11 = {}

i = 1

p = 1

step = 10

while i <= N:

p = (p * step + p) % MOD

step = (step * step) % MOD

i *= 2

cache10 = {0: 1}

i = 1

p = 10

while i <= N:

p = (p * 10) % MOD

i += 1

def action_force(action, value, size):

if action == action_unity:

return value

# return int(str(action) * size)

def action_composite(new_action, old_action):

if new_action == action_unity:

return old_action

return new_action

def value_binop(a, b, size):

# return (a * (10 ** size) + b) % MOD

full_up(value_table, value_binop)

for _q in range(Q):

l, r, d = map(int, input().split())

lazy_range_update(

action_table, value_table, l - 1, r, d,

action_composite, action_force, action_unity, value_binop)

ret = lazy_range_reduce(

action_table, value_table, 0, N, action_composite, action_force, action_unity,

value_binop, value_unity)

print(ret)

F